/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
 * in compliance with the License. You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software distributed under the License
 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
 * or implied. See the License for the specific language governing permissions and limitations under
 * the License.
 */

package com.google.common.collect;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.Beta;
import com.google.common.annotations.GwtIncompatible;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.base.MoreObjects;

import java.io.Serializable;
import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.NavigableMap;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeMap;
import javax.annotation.CheckForNull;

/**
 * An implementation of {@link RangeSet} backed by a {@link TreeMap}.
 *
 * @author Louis Wasserman
 * @since 14.0
 */
@Beta
@GwtIncompatible // uses NavigableMap
@ElementTypesAreNonnullByDefault
public class TreeRangeSet<C extends Comparable<?>> extends AbstractRangeSet<C>
        implements Serializable
{

    @VisibleForTesting
    final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;

    /**
     * Creates an empty {@code TreeRangeSet} instance.
     */
    public static <C extends Comparable<?>> TreeRangeSet<C> create()
    {
        return new TreeRangeSet<>(new TreeMap<Cut<C>, Range<C>>());
    }

    /**
     * Returns a {@code TreeRangeSet} initialized with the ranges in the specified range set.
     */
    public static <C extends Comparable<?>> TreeRangeSet<C> create(RangeSet<C> rangeSet)
    {
        TreeRangeSet<C> result = create();
        result.addAll(rangeSet);
        return result;
    }

    /**
     * Returns a {@code TreeRangeSet} representing the union of the specified ranges.
     *
     * <p>This is the smallest {@code RangeSet} which encloses each of the specified ranges. An
     * element will be contained in this {@code RangeSet} if and only if it is contained in at least
     * one {@code Range} in {@code ranges}.
     *
     * @since 21.0
     */
    public static <C extends Comparable<?>> TreeRangeSet<C> create(Iterable<Range<C>> ranges)
    {
        TreeRangeSet<C> result = create();
        result.addAll(ranges);
        return result;
    }

    private TreeRangeSet(NavigableMap<Cut<C>, Range<C>> rangesByLowerCut)
    {
        this.rangesByLowerBound = rangesByLowerCut;
    }

    @CheckForNull
    private transient Set<Range<C>> asRanges;
    @CheckForNull
    private transient Set<Range<C>> asDescendingSetOfRanges;

    @Override
    public Set<Range<C>> asRanges()
    {
        Set<Range<C>> result = asRanges;
        return (result == null) ? asRanges = new AsRanges(rangesByLowerBound.values()) : result;
    }

    @Override
    public Set<Range<C>> asDescendingSetOfRanges()
    {
        Set<Range<C>> result = asDescendingSetOfRanges;
        return (result == null)
                ? asDescendingSetOfRanges = new AsRanges(rangesByLowerBound.descendingMap().values())
                : result;
    }

    final class AsRanges extends ForwardingCollection<Range<C>> implements Set<Range<C>>
    {

        final Collection<Range<C>> delegate;

        AsRanges(Collection<Range<C>> delegate)
        {
            this.delegate = delegate;
        }

        @Override
        protected Collection<Range<C>> delegate()
        {
            return delegate;
        }

        @Override
        public int hashCode()
        {
            return Sets.hashCodeImpl(this);
        }

        @Override
        public boolean equals(@CheckForNull Object o)
        {
            return Sets.equalsImpl(this, o);
        }
    }

    @Override
    @CheckForNull
    public Range<C> rangeContaining(C value)
    {
        checkNotNull(value);
        Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(Cut.belowValue(value));
        if (floorEntry != null && floorEntry.getValue().contains(value))
        {
            return floorEntry.getValue();
        }
        else
        {
            // TODO(kevinb): revisit this design choice
            return null;
        }
    }

    @Override
    public boolean intersects(Range<C> range)
    {
        checkNotNull(range);
        Entry<Cut<C>, Range<C>> ceilingEntry = rangesByLowerBound.ceilingEntry(range.lowerBound);
        if (ceilingEntry != null
                && ceilingEntry.getValue().isConnected(range)
                && !ceilingEntry.getValue().intersection(range).isEmpty())
        {
            return true;
        }
        Entry<Cut<C>, Range<C>> priorEntry = rangesByLowerBound.lowerEntry(range.lowerBound);
        return priorEntry != null
                && priorEntry.getValue().isConnected(range)
                && !priorEntry.getValue().intersection(range).isEmpty();
    }

    @Override
    public boolean encloses(Range<C> range)
    {
        checkNotNull(range);
        Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
        return floorEntry != null && floorEntry.getValue().encloses(range);
    }

    @CheckForNull
    private Range<C> rangeEnclosing(Range<C> range)
    {
        checkNotNull(range);
        Entry<Cut<C>, Range<C>> floorEntry = rangesByLowerBound.floorEntry(range.lowerBound);
        return (floorEntry != null && floorEntry.getValue().encloses(range))
                ? floorEntry.getValue()
                : null;
    }

    @Override
    public Range<C> span()
    {
        Entry<Cut<C>, Range<C>> firstEntry = rangesByLowerBound.firstEntry();
        Entry<Cut<C>, Range<C>> lastEntry = rangesByLowerBound.lastEntry();
        if (firstEntry == null || lastEntry == null)
        {
            /*
             * Either both are null or neither is: Either the set is empty, or it's not. But we check both
             * to make the nullness checker happy.
             */
            throw new NoSuchElementException();
        }
        return Range.create(firstEntry.getValue().lowerBound, lastEntry.getValue().upperBound);
    }

    @Override
    public void add(Range<C> rangeToAdd)
    {
        checkNotNull(rangeToAdd);

        if (rangeToAdd.isEmpty())
        {
            return;
        }

        // We will use { } to illustrate ranges currently in the range set, and < >
        // to illustrate rangeToAdd.
        Cut<C> lbToAdd = rangeToAdd.lowerBound;
        Cut<C> ubToAdd = rangeToAdd.upperBound;

        Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(lbToAdd);
        if (entryBelowLB != null)
        {
            // { <
            Range<C> rangeBelowLB = entryBelowLB.getValue();
            if (rangeBelowLB.upperBound.compareTo(lbToAdd) >= 0)
            {
                // { < }, and we will need to coalesce
                if (rangeBelowLB.upperBound.compareTo(ubToAdd) >= 0)
                {
                    // { < > }
                    ubToAdd = rangeBelowLB.upperBound;
                    /*
                     * TODO(cpovirk): can we just "return;" here? Or, can we remove this if() entirely? If
                     * not, add tests to demonstrate the problem with each approach
                     */
                }
                lbToAdd = rangeBelowLB.lowerBound;
            }
        }

        Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(ubToAdd);
        if (entryBelowUB != null)
        {
            // { >
            Range<C> rangeBelowUB = entryBelowUB.getValue();
            if (rangeBelowUB.upperBound.compareTo(ubToAdd) >= 0)
            {
                // { > }, and we need to coalesce
                ubToAdd = rangeBelowUB.upperBound;
            }
        }

        // Remove ranges which are strictly enclosed.
        rangesByLowerBound.subMap(lbToAdd, ubToAdd).clear();

        replaceRangeWithSameLowerBound(Range.create(lbToAdd, ubToAdd));
    }

    @Override
    public void remove(Range<C> rangeToRemove)
    {
        checkNotNull(rangeToRemove);

        if (rangeToRemove.isEmpty())
        {
            return;
        }

        // We will use { } to illustrate ranges currently in the range set, and < >
        // to illustrate rangeToRemove.

        Entry<Cut<C>, Range<C>> entryBelowLB = rangesByLowerBound.lowerEntry(rangeToRemove.lowerBound);
        if (entryBelowLB != null)
        {
            // { <
            Range<C> rangeBelowLB = entryBelowLB.getValue();
            if (rangeBelowLB.upperBound.compareTo(rangeToRemove.lowerBound) >= 0)
            {
                // { < }, and we will need to subdivide
                if (rangeToRemove.hasUpperBound()
                        && rangeBelowLB.upperBound.compareTo(rangeToRemove.upperBound) >= 0)
                {
                    // { < > }
                    replaceRangeWithSameLowerBound(
                            Range.create(rangeToRemove.upperBound, rangeBelowLB.upperBound));
                }
                replaceRangeWithSameLowerBound(
                        Range.create(rangeBelowLB.lowerBound, rangeToRemove.lowerBound));
            }
        }

        Entry<Cut<C>, Range<C>> entryBelowUB = rangesByLowerBound.floorEntry(rangeToRemove.upperBound);
        if (entryBelowUB != null)
        {
            // { >
            Range<C> rangeBelowUB = entryBelowUB.getValue();
            if (rangeToRemove.hasUpperBound()
                    && rangeBelowUB.upperBound.compareTo(rangeToRemove.upperBound) >= 0)
            {
                // { > }
                replaceRangeWithSameLowerBound(
                        Range.create(rangeToRemove.upperBound, rangeBelowUB.upperBound));
            }
        }

        rangesByLowerBound.subMap(rangeToRemove.lowerBound, rangeToRemove.upperBound).clear();
    }

    private void replaceRangeWithSameLowerBound(Range<C> range)
    {
        if (range.isEmpty())
        {
            rangesByLowerBound.remove(range.lowerBound);
        }
        else
        {
            rangesByLowerBound.put(range.lowerBound, range);
        }
    }

    @CheckForNull
    private transient RangeSet<C> complement;

    @Override
    public RangeSet<C> complement()
    {
        RangeSet<C> result = complement;
        return (result == null) ? complement = new Complement() : result;
    }

    @VisibleForTesting
    static final class RangesByUpperBound<C extends Comparable<?>>
            extends AbstractNavigableMap<Cut<C>, Range<C>>
    {
        private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;

        /**
         * upperBoundWindow represents the headMap/subMap/tailMap view of the entire "ranges by upper
         * bound" map; it's a constraint on the *keys*, and does not affect the values.
         */
        private final Range<Cut<C>> upperBoundWindow;

        RangesByUpperBound(NavigableMap<Cut<C>, Range<C>> rangesByLowerBound)
        {
            this.rangesByLowerBound = rangesByLowerBound;
            this.upperBoundWindow = Range.all();
        }

        private RangesByUpperBound(
                NavigableMap<Cut<C>, Range<C>> rangesByLowerBound, Range<Cut<C>> upperBoundWindow)
        {
            this.rangesByLowerBound = rangesByLowerBound;
            this.upperBoundWindow = upperBoundWindow;
        }

        private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window)
        {
            if (window.isConnected(upperBoundWindow))
            {
                return new RangesByUpperBound<>(rangesByLowerBound, window.intersection(upperBoundWindow));
            }
            else
            {
                return ImmutableSortedMap.of();
            }
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> subMap(
                Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive)
        {
            return subMap(
                    Range.range(
                            fromKey, BoundType.forBoolean(fromInclusive),
                            toKey, BoundType.forBoolean(toInclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive)
        {
            return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive)
        {
            return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public Comparator<? super Cut<C>> comparator()
        {
            return Ordering.<Cut<C>>natural();
        }

        @Override
        public boolean containsKey(@CheckForNull Object key)
        {
            return get(key) != null;
        }

        @Override
        @CheckForNull
        public Range<C> get(@CheckForNull Object key)
        {
            if (key instanceof Cut)
            {
                try
                {
                    @SuppressWarnings("unchecked") // we catch CCEs
                    Cut<C> cut = (Cut<C>) key;
                    if (!upperBoundWindow.contains(cut))
                    {
                        return null;
                    }
                    Entry<Cut<C>, Range<C>> candidate = rangesByLowerBound.lowerEntry(cut);
                    if (candidate != null && candidate.getValue().upperBound.equals(cut))
                    {
                        return candidate.getValue();
                    }
                }
                catch (ClassCastException e)
                {
                    return null;
                }
            }
            return null;
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> entryIterator()
        {
            /*
             * We want to start the iteration at the first range where the upper bound is in
             * upperBoundWindow.
             */
            Iterator<Range<C>> backingItr;
            if (!upperBoundWindow.hasLowerBound())
            {
                backingItr = rangesByLowerBound.values().iterator();
            }
            else
            {
                Entry<Cut<C>, Range<C>> lowerEntry =
                        rangesByLowerBound.lowerEntry(upperBoundWindow.lowerEndpoint());
                if (lowerEntry == null)
                {
                    backingItr = rangesByLowerBound.values().iterator();
                }
                else if (upperBoundWindow.lowerBound.isLessThan(lowerEntry.getValue().upperBound))
                {
                    backingItr = rangesByLowerBound.tailMap(lowerEntry.getKey(), true).values().iterator();
                }
                else
                {
                    backingItr =
                            rangesByLowerBound
                                    .tailMap(upperBoundWindow.lowerEndpoint(), true)
                                    .values()
                                    .iterator();
                }
            }
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (!backingItr.hasNext())
                    {
                        return endOfData();
                    }
                    Range<C> range = backingItr.next();
                    if (upperBoundWindow.upperBound.isLessThan(range.upperBound))
                    {
                        return endOfData();
                    }
                    else
                    {
                        return Maps.immutableEntry(range.upperBound, range);
                    }
                }
            };
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator()
        {
            Collection<Range<C>> candidates;
            if (upperBoundWindow.hasUpperBound())
            {
                candidates =
                        rangesByLowerBound
                                .headMap(upperBoundWindow.upperEndpoint(), false)
                                .descendingMap()
                                .values();
            }
            else
            {
                candidates = rangesByLowerBound.descendingMap().values();
            }
            PeekingIterator<Range<C>> backingItr = Iterators.peekingIterator(candidates.iterator());
            if (backingItr.hasNext()
                    && upperBoundWindow.upperBound.isLessThan(backingItr.peek().upperBound))
            {
                backingItr.next();
            }
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (!backingItr.hasNext())
                    {
                        return endOfData();
                    }
                    Range<C> range = backingItr.next();
                    return upperBoundWindow.lowerBound.isLessThan(range.upperBound)
                            ? Maps.immutableEntry(range.upperBound, range)
                            : endOfData();
                }
            };
        }

        @Override
        public int size()
        {
            if (upperBoundWindow.equals(Range.all()))
            {
                return rangesByLowerBound.size();
            }
            return Iterators.size(entryIterator());
        }

        @Override
        public boolean isEmpty()
        {
            return upperBoundWindow.equals(Range.all())
                    ? rangesByLowerBound.isEmpty()
                    : !entryIterator().hasNext();
        }
    }

    private static final class ComplementRangesByLowerBound<C extends Comparable<?>>
            extends AbstractNavigableMap<Cut<C>, Range<C>>
    {
        private final NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound;
        private final NavigableMap<Cut<C>, Range<C>> positiveRangesByUpperBound;

        /**
         * complementLowerBoundWindow represents the headMap/subMap/tailMap view of the entire
         * "complement ranges by lower bound" map; it's a constraint on the *keys*, and does not affect
         * the values.
         */
        private final Range<Cut<C>> complementLowerBoundWindow;

        ComplementRangesByLowerBound(NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound)
        {
            this(positiveRangesByLowerBound, Range.<Cut<C>>all());
        }

        private ComplementRangesByLowerBound(
                NavigableMap<Cut<C>, Range<C>> positiveRangesByLowerBound, Range<Cut<C>> window)
        {
            this.positiveRangesByLowerBound = positiveRangesByLowerBound;
            this.positiveRangesByUpperBound = new RangesByUpperBound<>(positiveRangesByLowerBound);
            this.complementLowerBoundWindow = window;
        }

        private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> subWindow)
        {
            if (!complementLowerBoundWindow.isConnected(subWindow))
            {
                return ImmutableSortedMap.of();
            }
            else
            {
                subWindow = subWindow.intersection(complementLowerBoundWindow);
                return new ComplementRangesByLowerBound<>(positiveRangesByLowerBound, subWindow);
            }
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> subMap(
                Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive)
        {
            return subMap(
                    Range.range(
                            fromKey, BoundType.forBoolean(fromInclusive),
                            toKey, BoundType.forBoolean(toInclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive)
        {
            return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive)
        {
            return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public Comparator<? super Cut<C>> comparator()
        {
            return Ordering.<Cut<C>>natural();
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> entryIterator()
        {
            /*
             * firstComplementRangeLowerBound is the first complement range lower bound inside
             * complementLowerBoundWindow. Complement range lower bounds are either positive range upper
             * bounds, or Cut.belowAll().
             *
             * positiveItr starts at the first positive range with lower bound greater than
             * firstComplementRangeLowerBound. (Positive range lower bounds correspond to complement range
             * upper bounds.)
             */
            Collection<Range<C>> positiveRanges;
            if (complementLowerBoundWindow.hasLowerBound())
            {
                positiveRanges =
                        positiveRangesByUpperBound
                                .tailMap(
                                        complementLowerBoundWindow.lowerEndpoint(),
                                        complementLowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
                                .values();
            }
            else
            {
                positiveRanges = positiveRangesByUpperBound.values();
            }
            PeekingIterator<Range<C>> positiveItr = Iterators.peekingIterator(positiveRanges.iterator());
            Cut<C> firstComplementRangeLowerBound;
            if (complementLowerBoundWindow.contains(Cut.<C>belowAll())
                    && (!positiveItr.hasNext() || positiveItr.peek().lowerBound != Cut.<C>belowAll()))
            {
                firstComplementRangeLowerBound = Cut.belowAll();
            }
            else if (positiveItr.hasNext())
            {
                firstComplementRangeLowerBound = positiveItr.next().upperBound;
            }
            else
            {
                return Iterators.emptyIterator();
            }
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                Cut<C> nextComplementRangeLowerBound = firstComplementRangeLowerBound;

                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (complementLowerBoundWindow.upperBound.isLessThan(nextComplementRangeLowerBound)
                            || nextComplementRangeLowerBound == Cut.<C>aboveAll())
                    {
                        return endOfData();
                    }
                    Range<C> negativeRange;
                    if (positiveItr.hasNext())
                    {
                        Range<C> positiveRange = positiveItr.next();
                        negativeRange = Range.create(nextComplementRangeLowerBound, positiveRange.lowerBound);
                        nextComplementRangeLowerBound = positiveRange.upperBound;
                    }
                    else
                    {
                        negativeRange = Range.create(nextComplementRangeLowerBound, Cut.<C>aboveAll());
                        nextComplementRangeLowerBound = Cut.aboveAll();
                    }
                    return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
                }
            };
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator()
        {
            /*
             * firstComplementRangeUpperBound is the upper bound of the last complement range with lower
             * bound inside complementLowerBoundWindow.
             *
             * positiveItr starts at the first positive range with upper bound less than
             * firstComplementRangeUpperBound. (Positive range upper bounds correspond to complement range
             * lower bounds.)
             */
            Cut<C> startingPoint =
                    complementLowerBoundWindow.hasUpperBound()
                            ? complementLowerBoundWindow.upperEndpoint()
                            : Cut.<C>aboveAll();
            boolean inclusive =
                    complementLowerBoundWindow.hasUpperBound()
                            && complementLowerBoundWindow.upperBoundType() == BoundType.CLOSED;
            PeekingIterator<Range<C>> positiveItr =
                    Iterators.peekingIterator(
                            positiveRangesByUpperBound
                                    .headMap(startingPoint, inclusive)
                                    .descendingMap()
                                    .values()
                                    .iterator());
            Cut<C> cut;
            if (positiveItr.hasNext())
            {
                cut =
                        (positiveItr.peek().upperBound == Cut.<C>aboveAll())
                                ? positiveItr.next().lowerBound
                                : positiveRangesByLowerBound.higherKey(positiveItr.peek().upperBound);
            }
            else if (!complementLowerBoundWindow.contains(Cut.<C>belowAll())
                    || positiveRangesByLowerBound.containsKey(Cut.belowAll()))
            {
                return Iterators.emptyIterator();
            }
            else
            {
                cut = positiveRangesByLowerBound.higherKey(Cut.<C>belowAll());
            }
            Cut<C> firstComplementRangeUpperBound = MoreObjects.firstNonNull(cut, Cut.<C>aboveAll());
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                Cut<C> nextComplementRangeUpperBound = firstComplementRangeUpperBound;

                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (nextComplementRangeUpperBound == Cut.<C>belowAll())
                    {
                        return endOfData();
                    }
                    else if (positiveItr.hasNext())
                    {
                        Range<C> positiveRange = positiveItr.next();
                        Range<C> negativeRange =
                                Range.create(positiveRange.upperBound, nextComplementRangeUpperBound);
                        nextComplementRangeUpperBound = positiveRange.lowerBound;
                        if (complementLowerBoundWindow.lowerBound.isLessThan(negativeRange.lowerBound))
                        {
                            return Maps.immutableEntry(negativeRange.lowerBound, negativeRange);
                        }
                    }
                    else if (complementLowerBoundWindow.lowerBound.isLessThan(Cut.<C>belowAll()))
                    {
                        Range<C> negativeRange = Range.create(Cut.<C>belowAll(), nextComplementRangeUpperBound);
                        nextComplementRangeUpperBound = Cut.belowAll();
                        return Maps.immutableEntry(Cut.<C>belowAll(), negativeRange);
                    }
                    return endOfData();
                }
            };
        }

        @Override
        public int size()
        {
            return Iterators.size(entryIterator());
        }

        @Override
        @CheckForNull
        public Range<C> get(@CheckForNull Object key)
        {
            if (key instanceof Cut)
            {
                try
                {
                    @SuppressWarnings("unchecked")
                    Cut<C> cut = (Cut<C>) key;
                    // tailMap respects the current window
                    Entry<Cut<C>, Range<C>> firstEntry = tailMap(cut, true).firstEntry();
                    if (firstEntry != null && firstEntry.getKey().equals(cut))
                    {
                        return firstEntry.getValue();
                    }
                }
                catch (ClassCastException e)
                {
                    return null;
                }
            }
            return null;
        }

        @Override
        public boolean containsKey(@CheckForNull Object key)
        {
            return get(key) != null;
        }
    }

    private final class Complement extends TreeRangeSet<C>
    {
        Complement()
        {
            super(new ComplementRangesByLowerBound<C>(TreeRangeSet.this.rangesByLowerBound));
        }

        @Override
        public void add(Range<C> rangeToAdd)
        {
            TreeRangeSet.this.remove(rangeToAdd);
        }

        @Override
        public void remove(Range<C> rangeToRemove)
        {
            TreeRangeSet.this.add(rangeToRemove);
        }

        @Override
        public boolean contains(C value)
        {
            return !TreeRangeSet.this.contains(value);
        }

        @Override
        public RangeSet<C> complement()
        {
            return TreeRangeSet.this;
        }
    }

    private static final class SubRangeSetRangesByLowerBound<C extends Comparable<?>>
            extends AbstractNavigableMap<Cut<C>, Range<C>>
    {
        /**
         * lowerBoundWindow is the headMap/subMap/tailMap view; it only restricts the keys, and does not
         * affect the values.
         */
        private final Range<Cut<C>> lowerBoundWindow;

        /**
         * restriction is the subRangeSet view; ranges are truncated to their intersection with
         * restriction.
         */
        private final Range<C> restriction;

        private final NavigableMap<Cut<C>, Range<C>> rangesByLowerBound;
        private final NavigableMap<Cut<C>, Range<C>> rangesByUpperBound;

        private SubRangeSetRangesByLowerBound(
                Range<Cut<C>> lowerBoundWindow,
                Range<C> restriction,
                NavigableMap<Cut<C>, Range<C>> rangesByLowerBound)
        {
            this.lowerBoundWindow = checkNotNull(lowerBoundWindow);
            this.restriction = checkNotNull(restriction);
            this.rangesByLowerBound = checkNotNull(rangesByLowerBound);
            this.rangesByUpperBound = new RangesByUpperBound<>(rangesByLowerBound);
        }

        private NavigableMap<Cut<C>, Range<C>> subMap(Range<Cut<C>> window)
        {
            if (!window.isConnected(lowerBoundWindow))
            {
                return ImmutableSortedMap.of();
            }
            else
            {
                return new SubRangeSetRangesByLowerBound<>(
                        lowerBoundWindow.intersection(window), restriction, rangesByLowerBound);
            }
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> subMap(
                Cut<C> fromKey, boolean fromInclusive, Cut<C> toKey, boolean toInclusive)
        {
            return subMap(
                    Range.range(
                            fromKey,
                            BoundType.forBoolean(fromInclusive),
                            toKey,
                            BoundType.forBoolean(toInclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> headMap(Cut<C> toKey, boolean inclusive)
        {
            return subMap(Range.upTo(toKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public NavigableMap<Cut<C>, Range<C>> tailMap(Cut<C> fromKey, boolean inclusive)
        {
            return subMap(Range.downTo(fromKey, BoundType.forBoolean(inclusive)));
        }

        @Override
        public Comparator<? super Cut<C>> comparator()
        {
            return Ordering.<Cut<C>>natural();
        }

        @Override
        public boolean containsKey(@CheckForNull Object key)
        {
            return get(key) != null;
        }

        @Override
        @CheckForNull
        public Range<C> get(@CheckForNull Object key)
        {
            if (key instanceof Cut)
            {
                try
                {
                    @SuppressWarnings("unchecked") // we catch CCE's
                    Cut<C> cut = (Cut<C>) key;
                    if (!lowerBoundWindow.contains(cut)
                            || cut.compareTo(restriction.lowerBound) < 0
                            || cut.compareTo(restriction.upperBound) >= 0)
                    {
                        return null;
                    }
                    else if (cut.equals(restriction.lowerBound))
                    {
                        // it might be present, truncated on the left
                        Range<C> candidate = Maps.valueOrNull(rangesByLowerBound.floorEntry(cut));
                        if (candidate != null && candidate.upperBound.compareTo(restriction.lowerBound) > 0)
                        {
                            return candidate.intersection(restriction);
                        }
                    }
                    else
                    {
                        Range<C> result = rangesByLowerBound.get(cut);
                        if (result != null)
                        {
                            return result.intersection(restriction);
                        }
                    }
                }
                catch (ClassCastException e)
                {
                    return null;
                }
            }
            return null;
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> entryIterator()
        {
            if (restriction.isEmpty())
            {
                return Iterators.emptyIterator();
            }
            Iterator<Range<C>> completeRangeItr;
            if (lowerBoundWindow.upperBound.isLessThan(restriction.lowerBound))
            {
                return Iterators.emptyIterator();
            }
            else if (lowerBoundWindow.lowerBound.isLessThan(restriction.lowerBound))
            {
                // starts at the first range with upper bound strictly greater than restriction.lowerBound
                completeRangeItr =
                        rangesByUpperBound.tailMap(restriction.lowerBound, false).values().iterator();
            }
            else
            {
                // starts at the first range with lower bound above lowerBoundWindow.lowerBound
                completeRangeItr =
                        rangesByLowerBound
                                .tailMap(
                                        lowerBoundWindow.lowerBound.endpoint(),
                                        lowerBoundWindow.lowerBoundType() == BoundType.CLOSED)
                                .values()
                                .iterator();
            }
            Cut<Cut<C>> upperBoundOnLowerBounds =
                    Ordering.natural()
                            .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (!completeRangeItr.hasNext())
                    {
                        return endOfData();
                    }
                    Range<C> nextRange = completeRangeItr.next();
                    if (upperBoundOnLowerBounds.isLessThan(nextRange.lowerBound))
                    {
                        return endOfData();
                    }
                    else
                    {
                        nextRange = nextRange.intersection(restriction);
                        return Maps.immutableEntry(nextRange.lowerBound, nextRange);
                    }
                }
            };
        }

        @Override
        Iterator<Entry<Cut<C>, Range<C>>> descendingEntryIterator()
        {
            if (restriction.isEmpty())
            {
                return Iterators.emptyIterator();
            }
            Cut<Cut<C>> upperBoundOnLowerBounds =
                    Ordering.natural()
                            .min(lowerBoundWindow.upperBound, Cut.belowValue(restriction.upperBound));
            Iterator<Range<C>> completeRangeItr =
                    rangesByLowerBound
                            .headMap(
                                    upperBoundOnLowerBounds.endpoint(),
                                    upperBoundOnLowerBounds.typeAsUpperBound() == BoundType.CLOSED)
                            .descendingMap()
                            .values()
                            .iterator();
            return new AbstractIterator<Entry<Cut<C>, Range<C>>>()
            {
                @Override
                @CheckForNull
                protected Entry<Cut<C>, Range<C>> computeNext()
                {
                    if (!completeRangeItr.hasNext())
                    {
                        return endOfData();
                    }
                    Range<C> nextRange = completeRangeItr.next();
                    if (restriction.lowerBound.compareTo(nextRange.upperBound) >= 0)
                    {
                        return endOfData();
                    }
                    nextRange = nextRange.intersection(restriction);
                    if (lowerBoundWindow.contains(nextRange.lowerBound))
                    {
                        return Maps.immutableEntry(nextRange.lowerBound, nextRange);
                    }
                    else
                    {
                        return endOfData();
                    }
                }
            };
        }

        @Override
        public int size()
        {
            return Iterators.size(entryIterator());
        }
    }

    @Override
    public RangeSet<C> subRangeSet(Range<C> view)
    {
        return view.equals(Range.<C>all()) ? this : new SubRangeSet(view);
    }

    private final class SubRangeSet extends TreeRangeSet<C>
    {
        private final Range<C> restriction;

        SubRangeSet(Range<C> restriction)
        {
            super(
                    new SubRangeSetRangesByLowerBound<C>(
                            Range.<Cut<C>>all(), restriction, TreeRangeSet.this.rangesByLowerBound));
            this.restriction = restriction;
        }

        @Override
        public boolean encloses(Range<C> range)
        {
            if (!restriction.isEmpty() && restriction.encloses(range))
            {
                Range<C> enclosing = TreeRangeSet.this.rangeEnclosing(range);
                return enclosing != null && !enclosing.intersection(restriction).isEmpty();
            }
            return false;
        }

        @Override
        @CheckForNull
        public Range<C> rangeContaining(C value)
        {
            if (!restriction.contains(value))
            {
                return null;
            }
            Range<C> result = TreeRangeSet.this.rangeContaining(value);
            return (result == null) ? null : result.intersection(restriction);
        }

        @Override
        public void add(Range<C> rangeToAdd)
        {
            checkArgument(
                    restriction.encloses(rangeToAdd),
                    "Cannot add range %s to subRangeSet(%s)",
                    rangeToAdd,
                    restriction);
            TreeRangeSet.this.add(rangeToAdd);
        }

        @Override
        public void remove(Range<C> rangeToRemove)
        {
            if (rangeToRemove.isConnected(restriction))
            {
                TreeRangeSet.this.remove(rangeToRemove.intersection(restriction));
            }
        }

        @Override
        public boolean contains(C value)
        {
            return restriction.contains(value) && TreeRangeSet.this.contains(value);
        }

        @Override
        public void clear()
        {
            TreeRangeSet.this.remove(restriction);
        }

        @Override
        public RangeSet<C> subRangeSet(Range<C> view)
        {
            if (view.encloses(restriction))
            {
                return this;
            }
            else if (view.isConnected(restriction))
            {
                return new SubRangeSet(restriction.intersection(view));
            }
            else
            {
                return ImmutableRangeSet.of();
            }
        }
    }
}
